package com.ztom.top100;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 除法求值
 * <p>
 * https://leetcode-cn.com/problems/evaluate-division/
 *
 * @author ZhangTao
 */
public class Code85CalcEquation {

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 卧槽了, 真的牛逼, 我想不到啊啊啊
        // 已知条件可以转化为并查集,  a / b = 2.0 ==> parent[a]=b  weight[a]=2.0
        // 除法可以考察 分子分母是否在一个集合, 即可知道能否解答
        Map<String, Integer> idMap = new HashMap<>(equations.size() * 2);
        UnionFound unionFound = preHandle(equations, values, idMap);

        double[] res = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            String x = query.get(0);
            String y = query.get(1);
            Integer idx = idMap.get(x);
            Integer idy = idMap.get(y);
            if (idx == null || idy == null) {
                res[i] = -1.0D;
            } else {
                res[i] = unionFound.isConnected(idx, idy);
            }
        }

        return res;
    }

    private UnionFound preHandle(List<List<String>> equations, double[] values, Map<String, Integer> idMap) {
        // 有可能已知条件中每个分子分母都不一样
        UnionFound unionFound = new UnionFound(equations.size() * 2);
        int id = 0;
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            String x = equation.get(0);
            String y = equation.get(1);
            if (!idMap.containsKey(x)) {
                idMap.put(x, id++);
            }
            if (!idMap.containsKey(y)) {
                idMap.put(y, id++);
            }
            // 合并  x -> y  ==>  parent[x]=y, weight[x]
            unionFound.union(idMap.get(x), idMap.get(y), values[i]);
        }
        return unionFound;
    }

    public class UnionFound {
        /**
         * 坐标压缩, 给已知条件的每个分子分母依次编号
         */
        private final int[] parent;
        /**
         * 已知条件中, 分子 分母 的有向权重值
         */
        private final double[] weight;

        public UnionFound(int n) {
            this.parent = new int[n];
            this.weight = new double[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                weight[i] = 1.0D;
            }
        }

        public int findFather(int x) {
            if (x != parent[x]) {
                int p = parent[x];
                // x 的父指向当前父的父
                parent[x] = findFather(p);
                // x 的权重一路向上累乘
                weight[x] *= weight[p];
            }
            return x;
        }

        public void union(int x, int y, double value) {
            int fx = findFather(x);
            int fy = findFather(y);
            if (fx == fy) {
                return;
            }
            parent[fx] = fy;
            /**
             *      fx  --weight[fx]--> fy
             *      ^                   ^
             *      |                   |
             *   weight[x]           weight[y]
             *      |                   |
             *      x   --value-->      y
             *
             *  weight[x] * weight[fx] = value * weight[y]
             */
            weight[fx] = weight[y] * value / weight[x];
        }

        public double isConnected(int x, int y) {
            int fx = findFather(x);
            int fy = findFather(y);
            if (fx == fy) {
                return weight[x] / weight[y];
            } else {
                return -1.0D;
            }
        }
    }
}
